#include <iostream>
#include <queue>
#include <cassert>

const int N = 1.5e5 + 5;

int n, m, q;
int a[N], d[N];

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);

	std::freopen("clear.in", "r", stdin);
	std::freopen("clear.out", "w", stdout);

	std::cin >> n >> m >> q;
	for(int i = 1; i <= n; ++i) std::cin >> a[i];
	while(q--) {
		int l, r; std::cin >> l >> r;
		long long ans = 0;
		std::queue<std::pair<int, long long>> dq;
		d[l] = a[l], d[r+1] = -a[r];
		for(int i = l + 1; i <= r; ++i) d[i] = a[i] - a[i-1];
		for(int i = l; i <= r + 1; ++i) {
			int dt = d[i];
			if(!dq.empty() && dq.front().first == i - m) {
				dt += dq.front().second;
				ans += dq.front().second;
				dq.pop();
			}
			while(dt < 0) {
				assert(!dq.empty());
				long long t = std::min(dq.front().second, (long long)-dt);
				ans += t;
				dt += t;
				dq.front().second -= t;
				if(dt) dq.pop();
			}
			if(dt > 0) dq.emplace(i, dt);
		}
		std::cout << ans << "\n";
	}

	return 0;
}
